'''
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution:
    def minPathSumDfs(self, grid) -> int:
        rows = len(grid)
        cols = len(grid[0])
        result = []
        res = []
        the_min_dis = float("inf")
        def dfs(row,col,rows,cols,res):
            nonlocal the_min_dis
            if row==rows-1 and col==cols-1:
                res.append(grid[rows-1][cols-1])
                kk = __import__('copy').deepcopy(res)
                result.append(kk)
                the_min_dis = min(sum(kk),themindis)
                res.pop()
                return
            if col+1<cols:
                res.append(grid[row][col])
                dfs(row,col+1,rows,cols,res)
                res.pop()
            if row+1<rows:
                res.append(grid[row][col])
                dfs(row+1, col, rows, cols, res)
                res.pop()
        dfs(0,0,rows,cols,res)
        print(the_min_dis)
    def minPathSumDp(self, grid) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dp = [[sum(grid[0][0:j+1]) if i==0 else 0 for j in range(cols)] for i in range(rows)]
        print(dp)
        for i in range(1,rows):
            for j in range(cols):
                if j == 0:
                    dp[i][j] = grid[i][j]+dp[i-1][j]
                else:
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i][j]
        print(dp)
        print(dp[rows-1][cols-1])

if __name__ == '__main__':
    s = Solution()
    d = [
          [1,3,1],
          [1,5,1],
          [4,2,1]
        ]
    d1 = [[1,2],[1,1]]
    d2 = [[1,2],
          [5,6],
          [1,1]]
    # s.minPathSumDfs(d)
    s.minPathSumDp(d2)